package Q3;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public Queue<int[]> queue = new LinkedList<>();
    public boolean[][] flag;
    public int[] dx = {0, 0, 1, -1};
    public int[] dy = {1, -1, 0, 0};
    public int n; //行数
    public int m; //列数
    public int[][] arr;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists int整型ArrayList<ArrayList<>>
     * @return int整型
     */
    public int citys (ArrayList<ArrayList<Integer>> lists) {
        // write code here

        n = lists.size();
        m = lists.get(0).size();

        arr = new int[n][m];
        flag = new boolean[n][m];

        int index1 = 0;
        for (ArrayList<Integer> arrayList : lists) {
            int index2 = 0;
            for (int num : arrayList) {
                arr[index1][index2] = num;
                if (num == 1) {
                    queue.offer(new int[]{index1, index2});
                }
                index2++;
            }
            index1++;
        }

        return bfs();
    }

    public int bfs() {
        int ret = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            ret++;
            while (size > 0) {
                size--;
                int[] temp = queue.poll();
                int x = temp[0];
                int y = temp[1];
                flag[x][y] = true;
                for (int i = 0; i < 4; i++) {
                    int xx = x + dx[i];
                    int yy = y + dy[i];
                    if (xx >= 0 && xx < n && yy >= 0 && yy < m && !flag[xx][yy] && arr[xx][yy] == 1) {
                        queue.offer(new int[]{xx, yy});
                        flag[xx][yy] = true;
                    }
                }
            }
        }

        return ret;
    }
}